package com.kotlin

/**
 * kotlin写几个算法学习下
*/
import java.util.*

class Parentheses{
    private val LEFT_PAREN = '('
    private val RIGHT_PAREN = ')'
    private val LEFT_BRACE = '{'
    private val RIGHT_BRACE = '}'
    private val LEFT_BRACKET = '['
    private val RIGHT_BRACKET = ']'

    fun isBalanced(s: String): Boolean {
        val stack = Stack<Char>()
        for (i in 0 until s.length) {
            if (s[i] == LEFT_PAREN) stack.push(LEFT_PAREN)
            if (s[i] == LEFT_BRACE) stack.push(LEFT_BRACE)
            if (s[i] == LEFT_BRACKET) stack.push(LEFT_BRACKET)

            if (s[i] == RIGHT_PAREN) {
                if (stack.isEmpty()) return false
                if (stack.pop() !== LEFT_PAREN) return false
            } else if (s[i] == RIGHT_BRACE) {
                if (stack.isEmpty()) return false
                if (stack.pop() !== LEFT_BRACE) return false
            } else if (s[i] == RIGHT_BRACKET) {
                if (stack.isEmpty()) return false
                if (stack.pop() !== LEFT_BRACKET) return false
            }
        }
        return stack.isEmpty()
    }
}

class AddBracket {
    private val LEFT_PAREN = '('
    private val RIGHT_PAREN = ')'

    fun isDigt(c: Char): Boolean {
        return c in '0'..'9'
    }

    fun isOpt(c: Char):Boolean {
        return c in listOf('+', '-', '*', '/')
    }

    fun addBrackets(s:String) {
        val format = s.replace("\\s", "")

        val dataStack = Stack<String>()
        val optStack = Stack<String>()

        for (c in format) {
            if (isDigt(c)) {
                dataStack.push(c.toString())
            }
            if (isOpt(c)) {
                optStack.push(c.toString())
            }
            if (c == RIGHT_PAREN) {
                val d2 = dataStack.pop()
                val d1 = dataStack.pop()
                val opt = optStack.pop()
                dataStack.push("$LEFT_PAREN $d1 $opt $d2 $RIGHT_PAREN")
            }
        }

        println(dataStack)
    }

    fun InfixToPostfix(s:String) {
        val dataStack = Stack<String>()
        val optStack = Stack<String>()
        for (c in s) {
            if (isDigt(c)) {
                dataStack.push(c.toString())
            }
            if (isOpt(c)) {
                optStack.push(c.toString())
            }
            if (c == RIGHT_PAREN) {
                val d2 = dataStack.pop()
                val d1 = dataStack.pop()
                val opt = optStack.pop()
                dataStack.push("$d1$d2$opt")
            }
        }

        println(dataStack)
    }

    fun EvalutePostfix(s: String) {
        val dataStatck = Stack<Int>()

        for (c in s) {
            /*
            需要格外注意，要先将Char转化成String，然后在转化int，否则结果是int值
            */
            if (isDigt(c)) { dataStatck.push(c.toString().toInt()) }
            if (isOpt(c)) {
                val d2 = dataStatck.pop()
                val d1 = dataStatck.pop()
                when(c) {
                    '*' -> dataStatck.push(d1 * d2)
                    '+' -> dataStatck.push(d1 + d2)
                    '-' -> dataStatck.push(d1 - d2)
                    '/' -> dataStatck.push(d1 / d2)
                }
            }
        }

        println(dataStatck)
    }

}



fun main(args: Array<String>) {
    val tmp = AddBracket()
    tmp.addBrackets("1+2)*3-4)*5-6)))")
    tmp.InfixToPostfix("( 2 + ( ( 3 + 4 ) * ( 5 * 6 ) ) )")
    tmp.EvalutePostfix("234+56**+")
}